#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#include "../color_units.h"

/**
 * 给定100个人站成一圈，从第1个人开始依次报数。
 * 每数到3的人将会被淘汰，然后继续从下一个人开始报数。
 * 这个过程会一直持续，直到所有的人都被淘汰。
 * 请编写一个C语言程序来模拟这个过程，并且输出每一个被淘汰人的编号。
 * 要求：输出每一个被淘汰人的编号，每淘汰一个人输出一行，格式为："%d out \n"(每输出一次换行)
*/

#define ALL_NUM    	100 
#define COUNT_NUM	3
#define OUT_NUM		3


//    #define LINK_SHOW
//#define STATE_SHOW
//#define LEFT
typedef struct node{
	int No;
	struct node* next;
}node;

node* phead; //指向头节点的指针


 
int LinkInit(node* phead){  //创建环形链表
	node *pre = phead;
	
	for (int i=2;i<=ALL_NUM;i++){
		node* newNode = (struct node*)malloc(sizeof(node));
		pre->next = newNode;
		newNode->No = i;
		pre=newNode;
	}
	pre->next=phead;
#ifdef LINK_SHOW
	node* p=phead;
	
	PRINT_DEBUG("link message\n");
	printf("phead->No: %d\n",p->No);
	p=p->next;
	while(p!=phead){
		printf("posINlink: %d\t",p->No);
		printf("the next is: %d\n",p->next->No);
		p=p->next;
	}

#endif



}

void nodeDel(node* prevNode,node* p){
	prevNode->next=p->next;
	p->next=NULL;
	free(p);
}
/*
int getPNum(struct node* phead){ //创建循环链表并为每个结点赋值
	struct node* head = NULL;
	struct node* prev = NULL;

	for (int i=1;i<=ALL_NUM;i++){
		node* newNode=(struct node*)malloc(sizeof(node));
		newNode->No=i;
	}
}
*/

int main(void)
{
	int left;	/* 剩余人数 */
	//int pos;	/* 当前报数位置 */
	int step;	/* 当前报数 */

	//TODO
	phead=(struct node*)malloc(sizeof(struct node));
	phead->No=1;
	LinkInit(phead);
	//printf("%d\n",ptest->next->No);
	//printf("%d\n",ptest->No);

	left=100;
	//pos=1;
	step=1;     //报数计数器
	node* p=phead;
	node* ppre=phead;
	node* pn=phead;

	while(left>0){
		while (step < OUT_NUM) {
			step++;
			if(step==3) {ppre=p;} //因为此时指针P还没更新，指向的是现在计数器所指结点的前一个结点
			p=p->next;
		}
		if(p==phead) {
			phead=phead->next;
			//printf("the new phead is: %d\n",phead->No);
		} 
		//跳出循环，说明此时step==3,且p也指向该报3的结点
		printf("%d out \n",p->No);
#ifdef LEFT
		//node* head=phead;
		if(p->No==43|| p->No==70){
		node* tp=phead;
		int l=left;

		while(l>0){
			printf("No. %d\t",tp->No);
			printf("tp.No:%d",tp->No);
			tp=tp->next;
			l--;
		}}
#endif
		pn=p->next;
#ifdef STATE_SHOW
		PRINT_DEBUG("LINK STATE:\n");
		node* ptest1=phead;
		node* ptest2=p;
		node* ptest3=pn;
		printf("to be deleted No: %d\n",ptest2->No);
		printf("the next No: %d\n",ptest3->No);
		int tleft=left;
		
		while(tleft>0){
			PRINT_DEBUG("the state of cri-link:\n");
			printf("phead->No: %d\n",ptest1->No);
			ptest2=ptest2->next;
			while(ptest2!=phead){
				printf("posINlink: %d\t",ptest2->No);
				printf("the next is: %d\n",ptest2->next->No);
				ptest2=ptest2->next;
			}
			tleft--;
			printf("\n");
		}
#endif
		if (p!=NULL) nodeDel(ppre,p);
		left--;
		p=pn;
		step=1;
	}
	return 0;
}

 